package com.cdream.basic.algorithm.leetcode.stack;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author cdream
 * @date 6/27/21
 */
public class Question909 {

    public static void main(String[] args) {
        // System.out.println(JSONUtil.toJsonStr(new Question909().intToArray(36, 6)));
        // System.out.println("aba".substring(0,1));
        int[][] param = {
                {-1, -1, 19, 10, -1},
                {2, -1, -1, 6, -1},
                {-1, 17, -1, 19, 25},
                {25, -1, 20, -1, -1},
                {-1, -1, -1, -1, 15}};
        System.out.println(new Question909().snakesAndLadders(param));

    }
    int n = 0;

    public int snakesAndLadders(int[][] board) {
        n = board.length;
        if (board[0][0] != -1) {
            return -1;
        }
        int[] nums = new int[n * n + 1];
        boolean isRight = true;
        int idx = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = (isRight ? 0 : n - 1); isRight ? j < n : j >= 0; j += isRight ? 1 : -1) {
                nums[idx++] = board[i][j];
            }
            isRight = !isRight;
        }
        int ans = bfs(nums);
        return ans;
    }

    int bfs(int[] nums) {
        LinkedList<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> used = new HashMap<>();
        queue.offer(1);
        used.put(1, 0);
        while (!queue.isEmpty()) {
            int poll = queue.poll();
            int step = used.get(poll);
            if (poll == n*n) {
                return step;
            }
            for (int i = 1; i <= 6; i++) {
                int next = poll + i;
                if (next <= 0 || next > n * n) continue;
                if (nums[next] != -1) next = nums[next];
                if (used.containsKey(next)) continue;
                used.put(next, step + 1);
                queue.offer(next);
            }
        }
        return -1;
    }


}
